#include "AC_C.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


static void BuildStep1();
static void BuildStep2();
#ifdef _DEBUG
static void DEBUG_PRINT();
#endif


struct  tagKeyword
{
	char *data;
	int length;
};

typedef struct tagKeyword Keyword;

struct tagAC
{
	
	//关键字列表
	Keyword * KeyList;
	//关键字列表的容量
	unsigned int KeyListCapacity;
	//关键字列表中已经使用的大小
	unsigned int KeyListSize;
	//Goto表
	unsigned int (*GotoMap)[256+1];
	unsigned int TotalState;
    
    //Fail函数表
    unsigned int *Fail;
};

#define OUTPUT 256

static struct tagAC AC;

void AC_AddKeyword(char *key, int key_len)
{
	if(AC.KeyList==NULL)
	{
		AC.KeyList=(Keyword*)malloc(sizeof(Keyword)*8);
        memset(AC.KeyList,0,sizeof(Keyword)*8);
		AC.KeyListCapacity=8;
	}

	//当前增加的关键字超出了目前的关键字容量
	if(AC.KeyListSize+1>AC.KeyListCapacity)
	{
		AC.KeyList=(Keyword*)realloc(AC.KeyList,AC.KeyListCapacity*2);
		AC.KeyListCapacity*=2;
	}
	//增加关键字
	else 
	{
		AC.KeyList[AC.KeyListSize].data=(char *)malloc(key_len+1);
		if(AC.KeyList[AC.KeyListSize].data==NULL)
		{
			fprintf(stderr,"[%s:%d] Can't allocate memory for '%s'\n",__FILE__,__LINE__,key);
			return;
		}

		//拷贝关键字，并调整关键字计数
		memcpy(AC.KeyList[AC.KeyListSize].data,key,key_len);
		AC.KeyList[AC.KeyListSize].data[key_len]=0;
		AC.KeyList[AC.KeyListSize].length=key_len;
		AC.KeyListSize+=1;

	}
}

void AC_Destroy()
{
    int i=0;
    free(AC.GotoMap);
    free(AC.Fail);
    for(i=0; i<AC.KeyListSize; ++i)
    {
        free(AC.KeyList[i].data);
    }
    memset(&AC,0,sizeof(struct tagAC));
    
}

void AC_Build()
{
	int i=0;

	//队列写指针
	int WIndex=0;
	//队列读指针
	int RIndex=0;

	if(AC.GotoMap!=NULL)
		return;

	for(;i<AC.KeyListSize; ++i)
	{
		AC.TotalState+=AC.KeyList[i].length;
	}

	AC.GotoMap=(unsigned int (*)[256+1])malloc(AC.TotalState * (256+1) * sizeof(unsigned int));
	if(AC.GotoMap==NULL)
	{
		fprintf(stderr,"[%s:%d] Can't allocate memory for creating GotoMap\n",__FILE__,__LINE__);
		return;
	}

	memset(AC.GotoMap,0,AC.TotalState * (256+1) * sizeof(unsigned int));


    BuildStep1();
    DEBUG_PRINT(&AC);
    BuildStep2();
    DEBUG_PRINT(&AC);

}
void BuildStep1()
{
    int i=0;
    int NowState=0;
    int NextState=0;
    //当前是0状态，也要统计入内
    int StateCount=1;

	//构造GOTO表
	for(i=0; i<AC.KeyListSize; ++i)
	{
		int j=0;
        NowState=0;
		//建立GOTO路径
		for(;j<AC.KeyList[i].length; ++j)
		{
			unsigned char ch=AC.KeyList[i].data[j];

			if(AC.GotoMap[NowState][ch]==0)
			{
				StateCount+=1;
				NextState+=1;
				AC.GotoMap[NowState][ch]=NextState;
				NowState=NextState;
			}
			else
				NowState=AC.GotoMap[NowState][ch];
		}
		//设置OUTPUT
		AC.GotoMap[NowState][OUTPUT]=i+1;

	}

	//调整GOTO表的大小
	if(StateCount<AC.TotalState)
	{
		unsigned int (*tmp)[256+1]=AC.GotoMap;
		AC.GotoMap=(unsigned int (*)[256+1])malloc(StateCount * (256+1) *sizeof(unsigned int));

		if(AC.GotoMap==NULL)
		{
			fprintf(stderr,"[%s:%d] Can't allocate memory for resizing GotoMap\n",__FILE__,__LINE__);
			free(tmp);
			return;
		}
		//拷贝GOTO表
        AC.TotalState=StateCount;
		memcpy(AC.GotoMap,tmp,StateCount * (256+1) *sizeof(unsigned int));
		free(tmp);
	}

}

void BuildStep2()
{
    int WIndex=0;
    int RIndex=0;
	//状态队列
	int Queue[OUTPUT];
    int i=0;

	//利用Fail函数修改GOTO表
	AC.Fail=(unsigned int*)malloc(AC.TotalState+1);
    memset(AC.Fail,0,sizeof(unsigned int)*(AC.TotalState+1));

    //保存根节点的路径
    WIndex+=1;
	for(i=0; i<256; ++i)
	{
		if(AC.GotoMap[0][i]!=0)
        {
            Queue[WIndex]=AC.GotoMap[0][i];		
            WIndex=(WIndex+1)%OUTPUT;
        }
	}
    //开始修改
    while((RIndex=(RIndex+1)%OUTPUT)!=WIndex)
    {
        int state=Queue[RIndex];
        for(i=0; i<256; ++i)
        {
            //当前状态存在路径去下一状态
            if(AC.GotoMap[state][i]!=0)
            {
                int next_state=Queue[WIndex]=AC.GotoMap[state][i];
                WIndex=(WIndex+1)%OUTPUT;
                int next_fail=AC.Fail[AC.GotoMap[state][i]]=AC.GotoMap[AC.Fail[state]][i];

                //当前状态没有OUPUT函数，而当前状态的失败状态有OUTPUT函数
                if(AC.GotoMap[next_fail][OUTPUT]>0 && AC.GotoMap[next_state][OUTPUT]==0)
                    AC.GotoMap[next_state][OUTPUT]=AC.GotoMap[next_fail][OUTPUT];
            }
            else
            {
                AC.GotoMap[state][i]=AC.GotoMap[AC.Fail[state]][i];
            }
        }
    }

}

char *AC_Find4Len(const char *data, int data_len)
{
    int State=0;
    unsigned char *p=(unsigned char *)data;
    unsigned char *begin=(unsigned char *)data;

    while((p-begin)<data_len)
    {
        State=AC.GotoMap[State][*p];

        int FailIndex=AC.GotoMap[AC.Fail[State]][OUTPUT];
        int Index=AC.GotoMap[State][OUTPUT];

        if(Index>0 && Index!=FailIndex) 
        {
            //printf("Found '%s' in '%s'\n",AC.KeyList[Index-1].data,p+1);
            return data+(p+1-begin);
        }

        if(FailIndex>0)
        {
            //printf("Found '%s' in '%s'\n",AC.KeyList[FailIndex-1].data,p+1);
            return data+(p+1-begin);
        }

        ++p;
    }
    return NULL;
}

void DEBUG_PRINT()
{
#ifdef _DEBUG
    int i=0;
    int j=0;
    printf("---------------Goto-------------\n");
    for(i=0; i<AC.TotalState; ++i)
    {   
        printf("State %02d:   ",i);
        for(j=0; j<OUTPUT; ++j)
        {   
            if(AC.GotoMap[i][j]!=0)
                printf("%c:%d ",j,AC.GotoMap[i][j]);
        }   
        if(AC.GotoMap[i][OUTPUT]>0)
            printf("OUTPUT:%d",AC.GotoMap[i][OUTPUT]);

        printf("\n");
    }   

#endif
}

